More hyperbinary fun

Posted on September 28, 2009 by Brent

When I originally posed Challenge #12, a certain Dave posted a series of comments with some explorations and partial solutions to part II (the hyperbinary sequence). Although I gave the “solution” in my last post, no solution to any problem is ever the last word—there’s always more to explore, more connections to see! It’s worth taking another post to explore some of Dave’s discoveries and conjectures, and how they connect to my last post. I’ve used different notations, made up some terms, tried to simplify things where possible, and so on, but all the ideas in this post are fundamentally Dave’s.

First things first

Dave first noticed that

$h(2^k - 1) = 1$

for all $k \geq 0$ . I noted this in my previous post as well, but said only that this is “apparent” from thinking about the recursive construction I described. However, it’s worth going through a proof of this more formally; it’s a good example of a proof by induction. First, let’s recall the recurrence relation that defines the hyperbinary sequence:

$\begin{array}{rcll}h(0) &=& 1 \\ h(2n+1) &=& h(n) & \qquad \text{(O)}\\ h(2n+2) &=& h(n+1) + h(n) & \qquad \text{(E)}\end{array}$

Now we can show that $h(2^k - 1) = 1$ for $k \geq 0$ . First, the base case: when $k=0$ , $h(2^0 - 1) = h(0) = 1$ ; check!

Now, let’s suppose that $h(2^k - 1) = 1$ for some particular $k \geq 0$ ; this is called the inductive hypothesis, which I will abbreviate as IH. we want to show that $h(2^{k+1} - 1) = 1$ as well. $2^{k+1} - 1$ is obviously odd, so we want to apply rule (O). The only trick is to get it into the right form first:

$\begin{array}{rcll} h(2^{k+1} - 1) &=& h(2^{k+1} - 2 + 1) & \qquad \text{\{ arithmetic \}}\\ &=& h(2(2^k - 1) + 1) & \qquad \text{\{ factor \}}\\ &=& h(2^k - 1) & \qquad \text{\{ rule (O) \}} \\ &=& 1 & \qquad \text{\{ IH \}}\end{array}$

Presto! Since the thing we wanted to show is true when $k=0$ and is true for $k+1$ whenever it is true for $k$ , by induction it must be true for all $k \geq 0$ .

Second things, third things…

But Dave then went on to notice that this sort of pattern isn’t unique to 1. For example,

$h(3 \cdot 2^k - 1) = 2$

for $k \geq 0$ , and

$h(5 \cdot 2^k - 1) = h(7 \cdot 2^k - 1) = 3$

also for $k \geq 0$ . Dave conjectured that this generalizes, and indeed it does: most generally, we can say that

$h(p \cdot 2^k - 1) = h(p - 1)$

for $k \geq 0$ . That is, once a certain number occurs at position $p - 1$ , it will keep occurring in a regular pattern after that, at every position of the form $p \cdot 2^k - 1$ . Note that $h(2^k - 1) = 1$ is a special case with $p = 1$ .

Why is this? Intuitively, it’s because of the “copying”—the blue numbers in my previous post. Once a number occurs, it will keep getting copied, but with the distance between the copies doubling each time. But again, this is worth proving formally. I’ll let you do this one—the proof by induction is similar to the proof above!

But why do occurrences of 1 correspond to $p = 1$ , and occurrences of 2 to $p = 3$ , and occurrences of 3 to $p = 5$ and $p = 7$ , and so on? Are there any patterns to be found here? This is what Dave explored next; let’s follow.

Primary occurrences and the inverse of h

Let’s think a little more about this equation $h(p \cdot 2^k - 1) = h(p - 1)$ . Let’s suppose that $p$ is odd (if it isn’t, we can always take another factor of two out of it to combine with the $2^k$ ). Notice that $p \cdot 2^k - 1$ is always odd, except when $k = 0$ (in which case $p \cdot 2^k - 1 = p - 1$ , which is even). Moreover, we can always write any odd number in the form $p \cdot 2^k - 1$ , where $p$ is odd: just add one, and factor out as many copies of 2 as possible. For example, $11 = 12 - 1 = 3 \cdot 2^2 - 1$ .

This means that if $q$ is any odd number, we can write it in the form $q = p \cdot 2^k - 1$ , and so $h(q) = h(p-1)$ : that is, every odd position in the hyperbinary sequence is just copied from an earlier even position. Of course, this can also be seen from the recursive construction in my previous post; but now we have really proved it! And what about the even positions? The values of the hyperbinary sequence at even positions are obtained by adding, rather than copying. If $n$ occurs at an even position, we will call it a primary occurrence of $n$ .

The nice thing about primary occurrences is that (a) there are only finitely many primary occurrences of any particular $n$ (challenge: prove this!), and (b) once we know the positions of the primary occurrences of $n$ , we know the positions of all the occurrences of $n$ : they are at positions of the form $p \cdot 2^k - 1$ , where $p - 1$ is a primary occurrence.

So, given $n$ , can we find all its primary occurrences? Essentially we are asking if we can compute $h^{-1}$ (by which I mean the inverse relation of $h$ ; since $h$ is not injective its inverse is obviously not a function), but leaving out non-primary occurrences since we can easily find those from primary ones. Let’s start by making a table with some small values of $n$ :

n	Primary occurrences
1	0
2	2
3	4, 6
4	8, 14
5	10, 12, 16, 30
6	32, 62
7	18, 22, 24, 28, 64, 126
8	20, 26, 128, 254
9	34, 46, 48, 60, 256, 510
10	38, 56, 512, 1022
11	36, 40, 54, 58, 66, 94, 96, 124, 1024, 2046
12	44, 50, 2048, 4094
13	42, 52, 70, 78, 112, 120, 130, 190, 192, 252, 4096, 8190
14	68, 80, 110, 122, 8192, 16382
15	72, 118, 258, 382, 384, 508, 16384, 32766
16	92, 98, 134, 158, 224, 248, 32768, 65534

Do you see any patterns? If so, can you prove them by induction? I’ll talk about a few in my next post. But I still don’t know whether there’s an effective way to compute $h^{-1}(n)$ !

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

This entry was posted in challenges, induction, pattern, proof, recursion, sequences, solutions and tagged hyperbinary, induction. Bookmark the permalink.

12 Responses to More hyperbinary fun

Dave says:

September 28, 2009 at 5:07 pm

I’m still thinking about how to find those “primary occurrences” (great way of phrasing that, by the way). I certainly prefer reading your interpretations of my solutions to my own jumbled mess of ideas. I always learn a great deal about notation from your site. I found the same thing when you interpreted my solution to the “cookie problem.” Thanks again and please keep up the great work.
Brent says:

September 28, 2009 at 7:54 pm

Great, let me know if you have any good ideas about finding primary occurrences! (I actually suspect—just a gut feeling—that the general problem is rather difficult, but don’t let that dissuade you. =) And I’m very glad to hear that you appreciate my interpretation–I take great joy in understanding other people’s good ideas and then re-presenting them in ways that are as clear and widely accessible as possible.
Fergal Daly says:

October 4, 2009 at 8:14 pm

In the table, the number of primary occurrences of N seems to be euler-phi(N). I wish I had any time to figure out why but I don’t.
Brendan says:

October 5, 2009 at 5:55 am

Hi Brent,

great series…got pointed here by a post over at division by zero which mentioned that great calkin-wilf tree. i came at this problem from a binary representation perspective, counting when a 10 could be represented as (01 + 01), which then opens up a new slot for any higher digits…. i was sad to see jason had worked out most of the details over a year ago, but i’ll keep working on it.

that said, it does suggest how to construct the largest primary occurrence of n. if you take a sequence of 1s (2^k – 1), there is one way to represent that number. however, if you set the last digit to 0 (2^k – 2), you now have choices (and you’ve made an even number). 2^1 can be represented as 2^0+2^0. and now, since there are no longer any 2^1s, 2^2 can be represented as 2^1+2^1, and so on. you end up with an alternative representation for each digit, plus the original representation, or k representations.

more formally:
h(2^n – 2)=n
for n=1, h(2-2)=h(0)=1
h(2^(n+1) – 2)=h(2^n – 1)+h(2^n – 2)=1+n

i say this is the largest primary occurrence because, intuitively, adding any digits (except leading 0s) will either add “choices” or make the number odd. i’ve already stayed up too late already, however, so i’ll have to leave the proof for later. the glaring 4,8,16,32,64,128…pattern in the chart above for the second largest occurrences will also have to wait until tomorrow.

cheers!
Brendan says:

October 5, 2009 at 6:06 am

just kidding, that’s the second easiest representation, a 1 followed by k-1 0s.

h(2^k)=k+1
for k=0, h(2^0)=h(1)=h(0)=1
h(2^(k+1))=h(2^k)+h(2^k – 1)=(k+1)+1=k+2

so, for n=10, 2^9=512; n=11, 2^10=1024, etc.

harder to prove that this one is the “second largest primary occurrence,” though.
Brent says:

October 5, 2009 at 7:01 am

Fergal: By golly, you’re right! I hadn’t noticed that. Hopefully someone will be able to prove it.

Brendan: good work! Indeed, those are the largest and second largest primary occurrences—which you can see intuitively by thinking about the recursive construction method I explained in a previous post. Proving it formally should not be too bad, I think, if you use the intuition to guide you—I think the hardest part would just be figuring out the correct (and sufficiently strong) inductive hypotheses.
Brendan says:

October 5, 2009 at 11:30 pm

the inverse relation is probably well beyond my number theory ability, but i’m enjoying playing with some of these easier patterns.

to generalize my findings above, i thought i’d show a closed form of h for binary numbers made by a string of p 1s and then q 0s (eg for 1110000 p=3, q=4). formatting in these comments makes it a little hard to follow, but hopefully this is clear. i also haven’t done an induction proof with two variables in a lot of years, but i think i have this right. the following depends on
h(2^n – 2)=n
h(p*2^k – 1) = h(p-1)

assume:
h(2^(p+q) – 2^q) = 1+pq
the base case would just be h(2^k -1), where q is 0 and p=k
h(2^(p+q+1) – 2^(q+1))=h(2^(p+q) – 2^q)+h(2^(p+q) – 2^q – 1)
the first term is assumption, so is equal to 1+pq, the second term:
h(2^(p+q) – 2^q – 1)=h((2^p)(2^q) – 2^q – 1)=h((2^p – 1)(2^q) – 1)
=h((2^p – 1) – 1)=h(2^p – 2)=p
summing the two terms
h(2^(p+(q+1)) – 2^(q+1))=1+pq+p=1+(q+1)p

looking at this now, would i need to hold q constant now and show the same for p+1?

the most interesting result of this (to me) is that this sets a lower limit for the number of primary occurrences of n as the number of divisors (including 1) of (n-1). for instance, n=13: 12 has 6 divisors and 6 of 13’s primary occurrences do indeed happen at numbers with binary representations of p 1s and q 0s where p*q=12. it also means that there are only two primary occurrences of this form for primes+1.

hopefully these aren’t blatantly obvious results!
Brent says:

October 6, 2009 at 4:01 pm

Brendan: Very cool! Glad you’re having fun. =) This is definitely not blatantly obvious, and it looks good. Re: your proof, you actually don’t need to go back and hold q constant and show it for p+1; the reason is that your base case holds for any value of p. If you only had a base case for p=0 and q=0 then you would have to do the induction for p as well.
Pingback: Hyperbinary conjecture seeking proof for a good time, long walks on the beach « The Math Less Traveled
Pingback: The hyperbinary sequence and the Calkin-Wilf tree « The Math Less Traveled
Pingback: Hyperbinary numbers and amateur-hour number theory « An Extremely Satisfactory Totalitarianism
Pingback: The hyperbinary sequence and the Calkin-Wilf tree | The Math Less Traveled

Comments are closed.